package src.leetcode.backtrack.medium_0093;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class restoreIpAddresses {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.restoreIpAddresses("25525511135"));
    }
}

// 方法二：回溯
class Solution {
    List<String> res = new ArrayList<>();
    List<Integer> indexes = new ArrayList<>();
    String s;

    public List<String> restoreIpAddresses(String s) {
        this.s = s;
        indexes.add(0);
        dfs(0);
        return res;
    }

    private void dfs(int start) {
        if(indexes.size() == 4){
            if(check(start, s.length())){
                String as = s.substring(indexes.get(0), indexes.get(1)) + "."
                        + s.substring(indexes.get(1), indexes.get(2)) + "."
                        + s.substring(indexes.get(2), indexes.get(3)) + "."
                        + s.substring(indexes.get(3));
                res.add(as);
            }
            return;
        }

        for(int i = start + 1; i < s.length(); i++){
            if(!check(start, i)){
                break;
            }

            indexes.add(i);
            dfs(i);
            indexes.remove(indexes.size() - 1);
        }
    }

    private boolean check(int start, int end) {
        if (s.charAt(start) == '0' && start + 1 < end) return false;
        int sum = 0;
        for (; start < end; start++) {
            sum = sum * 10 + s.charAt(start) - '0';
            if (sum > 255) return false;
        }
        return true;
    }
}

// 方法一：暴力
//class Solution {
//    List<String> res = new ArrayList<>();
//    String s;
//
//    public List<String> restoreIpAddresses(String s) {
//        this.s = s;
//        int n = s.length();
//        for (int i = 1; i < n; i++) {
//            if (!check(0, i)) break;
//            for (int j = i + 1; j < n; j++) {
//                if (!check(i, j)) break;
//                for (int k = j + 1; k < n; k++) {
//                    if (!check(j, k)) break;
//                    if (check(k, n)) {
//                        String sb = s.substring(0, i) + "." +
//                                s.substring(i, j) + "." +
//                                s.substring(j, k) + "." +
//                                s.substring(k, n);
//                        res.add(sb);
//                    }
//                }
//            }
//        }
//        return res;
//    }
//
//    private boolean check(int start, int end) {
//        if (s.charAt(start) == '0' && start + 1 < end) return false;
//        int sum = 0;
//        for (; start < end; start++) {
//            sum = sum * 10 + s.charAt(start) - '0';
//            if (sum > 255) return false;
//        }
//        return true;
//    }
//}